package org.algorithm.biubiu.wheel_1.链表;

import org.algorithm.biubiu.wheel_1.common.ListNode;
import org.junit.Test;

/**
 * @author jiazhaoxin
 * @Date 2022/2/18
 * @Desc {https://leetcode-cn.com/problems/reorder-list/submissions/}
 */
public class 链表重排 {


    @Test
    public void test(){
//        reorderList(ListNode.build(1,2));
        ListNode build = ListNode.build(1, 2);
        ListNode build2 = ListNode.build(3, 4);
        mergeList(build,build2);

    }

    public void reorderList(ListNode head) {
        if(head==null||head.next==null){
            return;
        }
        ListNode slowIndex = head, fastIndex = head;
        while(fastIndex.next!=null&&fastIndex.next.next!=null){
            slowIndex = slowIndex.next;
            fastIndex = fastIndex.next.next;
        }
        ListNode behindNode = slowIndex.next;
        // if(fastIndex!=head && fastIndex.next!=null){
        //     behindNode = fastIndex;
        // }else{
        //     behindNode = slowIndex.next;
        // }
        slowIndex.next = null;
        //反转后半部分的链表
        behindNode = resvert(behindNode);
        //重新拼接链表
        mergeList(head,behindNode);
    }

    public ListNode resvert(ListNode node){
        ListNode left = node;
        ListNode right = node.next;;
        left.next = null;
        while(right!=null){
            ListNode next = right.next;
            right.next = left;
            left = right;
            right = next;
        }
        return left;
    }

    public void mergeList(ListNode target, ListNode source) {
        ListNode index1;
        ListNode index2;
        while(target!=null&&source!=null){
            index1 = target.next;
            index2 = source.next;

            target.next =source;
            source.next = index1;
            target = index1;
            source= index2;
        }
    }
}
